package org.basis.algorithm.list;

import java.util.HashMap;

/**
 * 拷贝带有随机指针的链表
 *
 * @author Mr_wenpan@163.com 2021/12/14 10:49
 */
public class CopyListWithRandom {

    public static void main(String[] args) {
        Node head = null;
        Node res1 = null;
        Node res2 = null;
        printRandLinkedList(head);
        res1 = copyByHashTable(head);
        printRandLinkedList(res1);
        res2 = copyByPoint(head);
        printRandLinkedList(res2);
        printRandLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);

        head.random = head.next.next.next.next.next; // 1 -> 6
        head.next.random = head.next.next.next.next.next; // 2 -> 6
        head.next.next.random = head.next.next.next.next; // 3 -> 5
        head.next.next.next.random = head.next.next; // 4 -> 3
        head.next.next.next.next.random = null; // 5 -> null
        head.next.next.next.next.next.random = head.next.next.next; // 6 -> 4

        printRandLinkedList(head);
        res1 = copyByHashTable(head);
        printRandLinkedList(res1);
        res2 = copyByPoint(head);
        printRandLinkedList(res2);
        printRandLinkedList(head);
        System.out.println("=========================");

    }

    /**
     * 通过hash表来实现随机指针链表拷贝
     * 时间复杂度O（N） 空间复杂度 O(N)
     */
    public static Node copyByHashTable(Node head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new Node(head.data);
        }
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            // 每个对象的内存地址不一样，所以在hash表里不会存储被覆盖的情况（这里是以每个节点的内存地址为hash key）
            // key: 原节点，value：原节点的拷贝节点
            map.put(cur, new Node(cur.data));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            Node copyNode = map.get(cur);
            Node copyNext = map.get(cur.next);
            Node copyRandom = map.get(cur.random);
            copyNode.next = copyNext;
            copyNode.random = copyRandom;
            cur = cur.next;
        }

        return map.get(head);
    }

    /**
     * 通过指针的方式拷贝
     * 时间复杂度O（N）空间复杂度 O（1）
     */
    public static Node copyByPoint(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;

        // 每个节点都拷贝一份，并且就放在他的后面
        while (cur != null) {
            next = cur.next;
            Node copy = new Node(cur.data);
            cur.next = copy;
            copy.next = next;
            cur = next;
        }

        // 设置随机指针
        cur = head;
        Node copy;
        while (cur != null) {
            copy = cur.next;
            copy.random = cur.random;
            cur = cur.next.next;
        }

        // 将拷贝链表拆出来
        cur = head;
        Node newHead = head.next;
        while (cur != null) {
            copy = cur.next;
            next = cur.next.next;
            cur.next = next;
            cur = next;
            copy.next = next == null ? null : next.next;
        }

        return newHead;
    }

    public static void printRandLinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.random == null ? "- " : cur.random.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

/**
 * 带随机指针的节点
 */
class Node {
    public int data;
    public Node next;
    public Node random;

    public Node() {

    }

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next, Node random) {
        this.data = data;
        this.next = next;
        this.random = random;
    }

}
